{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Graph Connectivity With Threshold"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #union-find #array #math #number-theory"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #并查集 #数组 #数学 #数论"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: areConnected"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #带阈值的图连通性"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有 <code>n</code> 座城市，编号从 <code>1</code> 到 <code>n</code> 。编号为 <code>x</code> 和 <code>y</code> 的两座城市直接连通的前提是： <code>x</code> 和 <code>y</code> 的公因数中，至少有一个 <strong>严格大于</strong> 某个阈值 <code>threshold</code> 。更正式地说，如果存在整数 <code>z</code> ，且满足以下所有条件，则编号 <code>x</code> 和 <code>y</code> 的城市之间有一条道路：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>x % z == 0</code></li>\n",
    "\t<li><code>y % z == 0</code></li>\n",
    "\t<li><code>z > threshold</code></li>\n",
    "</ul>\n",
    "\n",
    "<p>给你两个整数 <code>n</code> 和 <code>threshold</code> ，以及一个待查询数组，请你判断每个查询<code> queries[i] = [a<sub>i</sub>, b<sub>i</sub>]</code> 指向的城市 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 是否连通（即，它们之间是否存在一条路径）。</p>\n",
    "\n",
    "<p>返回数组 <code>answer</code> ，其中<code>answer.length == queries.length</code> 。如果第 <code>i</code> 个查询中指向的城市 <code>a<sub>i</sub></code> 和 <code>b<sub>i</sub></code> 连通，则 <code>answer[i]</code> 为 <code>true</code> ；如果不连通，则 <code>answer[i]</code> 为 <code>false</code> 。</p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/18/ex1.jpg\" style=\"width: 382px; height: 181px;\" /></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, threshold = 2, queries = [[1,4],[2,5],[3,6]]\n",
    "<strong>输出：</strong>[false,false,true]\n",
    "<strong>解释：</strong>每个数的因数如下：\n",
    "1:   1\n",
    "2:   1, 2\n",
    "3:   1, <strong>3</strong>\n",
    "4:   1, 2, <strong>4</strong>\n",
    "5:   1, <strong>5</strong>\n",
    "6:   1, 2, <strong>3</strong>, <strong>6</strong>\n",
    "所有大于阈值的的因数已经加粗标识，只有城市 3 和 6 共享公约数 3 ，因此结果是： \n",
    "[1,4]   1 与 4 不连通\n",
    "[2,5]   2 与 5 不连通\n",
    "[3,6]   3 与 6 连通，存在路径 3--6\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/18/tmp.jpg\" style=\"width: 532px; height: 302px;\" /></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 6, threshold = 0, queries = [[4,5],[3,4],[3,2],[2,6],[1,3]]\n",
    "<strong>输出：</strong>[true,true,true,true,true]\n",
    "<strong>解释：</strong>每个数的因数与上一个例子相同。但是，由于阈值为 0 ，所有的因数都大于阈值。因为所有的数字共享公因数 1 ，所以所有的城市都互相连通。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/10/16/ex3.jpg\" style=\"width: 282px; height: 282px;\" /></p>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, threshold = 1, queries = [[4,5],[4,5],[3,2],[2,3],[3,4]]\n",
    "<strong>输出：</strong>[false,false,false,false,false]\n",
    "<strong>解释：</strong>只有城市 2 和 4 共享的公约数 2 严格大于阈值 1 ，所以只有这两座城市是连通的。\n",
    "注意，同一对节点 [x, y] 可以有多个查询，并且查询 [x，y] 等同于查询 [y，x] 。\n",
    "</pre>\n",
    "\n",
    "<p> </p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 <= n <= 10<sup>4</sup></code></li>\n",
    "\t<li><code>0 <= threshold <= n</code></li>\n",
    "\t<li><code>1 <= queries.length <= 10<sup>5</sup></code></li>\n",
    "\t<li><code>queries[i].length == 2</code></li>\n",
    "\t<li><code>1 <= a<sub>i</sub>, b<sub>i</sub> <= cities</code></li>\n",
    "\t<li><code>a<sub>i</sub> != b<sub>i</sub></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [graph-connectivity-with-threshold](https://leetcode.cn/problems/graph-connectivity-with-threshold/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [graph-connectivity-with-threshold](https://leetcode.cn/problems/graph-connectivity-with-threshold/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['6\\n2\\n[[1,4],[2,5],[3,6]]', '6\\n0\\n[[4,5],[3,4],[3,2],[2,6],[1,3]]', '5\\n1\\n[[4,5],[4,5],[3,2],[2,3],[3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        p = [i for i in range(n + 1)]\n",
    "        size = [1] * (n + 1)\n",
    "        def find(i):\n",
    "            if p[i] != i:\n",
    "                p[i] = find(p[i])\n",
    "            return p[i]\n",
    "        def merge(i, j):\n",
    "            pi, pj = find(i), find(j)\n",
    "            if size[pi] < size[pj]:\n",
    "                p[pi] = pj\n",
    "            elif size[pi] == size[pj]:\n",
    "                p[pi] = pj\n",
    "                size[pj] += 1\n",
    "            else:\n",
    "                p[pj] = pi\n",
    "        \n",
    "        used = [False] * (n // 2 + 1)    \n",
    "        for base in range(threshold + 1, n // 2 + 1):\n",
    "            cur = base * 2\n",
    "            while cur <= n:\n",
    "                if cur <= n // 2:\n",
    "                    used[cur] = True\n",
    "                merge(base, cur)\n",
    "                cur += base\n",
    "        \n",
    "        ans = [False] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            ans[i] = (find(x) == find(y))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.size[fx] < self.size[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.size[fx] += self.size[fy]\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        uf = UnionFind(n + 1)\n",
    "        for i in range(threshold + 1, n):\n",
    "            for j in range(i * 2, n + 1, i):\n",
    "                uf.union(i, j)\n",
    "        ans = []\n",
    "        for u, v in queries:\n",
    "            if uf.find(u) == uf.find(v):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans\n",
    "        ans = []\n",
    "        for u, v in queries:\n",
    "            if uf.find(u) == uf.find(v):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        p = list(range(n + 1))\n",
    "        if threshold == 0: \n",
    "            return [True] * len(queries)\n",
    "\n",
    "        def find(x):\n",
    "            if x != p[x]:\n",
    "                p[x] = find(p[x])\n",
    "            return p[x]\n",
    "\n",
    "        for z in range(threshold + 1, n):\n",
    "            for i in range(z * 2, n + 1, z):\n",
    "                p[find(i)] = find(i - z)\n",
    "        \n",
    "        n = len(queries)\n",
    "        ans = [False] * n\n",
    "        for i, (a, b) in enumerate(queries):\n",
    "            if find(a) == find(b):\n",
    "                ans[i] = True\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        if threshold==0:\n",
    "            return [True]*len(queries)\n",
    "        fa=[ i for i in range(n+2)]\n",
    "        def find(x:int)->int:\n",
    "            while x!=fa[x]:\n",
    "                fa[x]=fa[fa[x]]\n",
    "                x=fa[x]\n",
    "            return x\n",
    "        for i in range(threshold+1,n+1):\n",
    "            j=2\n",
    "            while i*j<=n:\n",
    "                fai=find(i)\n",
    "                faj=find(i*j)\n",
    "                fa[fai]=faj\n",
    "                # print(i,i*j)\n",
    "                # pre=i*j\n",
    "                j+=1\n",
    "        ans=[]\n",
    "        # for i in range(threshold+1,n+1):\n",
    "        #     print(find(i))\n",
    "        for x,y in queries:\n",
    "            fax=find(x)\n",
    "            fay=find(y)\n",
    "            if fax==fay:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        if threshold==0:\n",
    "            return [True]*len(queries)\n",
    "        fa=[ i for i in range(n+2)]\n",
    "        def find(x:int)->int:\n",
    "            while x!=fa[x]:\n",
    "                fa[x]=fa[fa[x]]\n",
    "                x=fa[x]\n",
    "            return x\n",
    "        for i in range(threshold+1,n+1):\n",
    "            j=2\n",
    "            while i*j<=n:\n",
    "                fai=find(i)\n",
    "                faj=find(i*j)\n",
    "                fa[fai]=faj\n",
    "                j+=1\n",
    "        ans=[]\n",
    "        for x,y in queries:\n",
    "            fax=find(x)\n",
    "            fay=find(y)\n",
    "            if fax==fay:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\r\n",
    "        if not threshold:\r\n",
    "            return [True]*len(queries)\r\n",
    "            \r\n",
    "        # 并查集\r\n",
    "        unions = list(range(n+1))\r\n",
    "        def find(i):\r\n",
    "            if (i!=unions[i]):\r\n",
    "                unions[i] = find(unions[i])\r\n",
    "                return unions[i]\r\n",
    "            else:return i\r\n",
    "\r\n",
    "        # 欧拉筛\r\n",
    "        primes = []\r\n",
    "        for t in range(threshold+1,n//2+1):\r\n",
    "            if unions[t]==t:\r\n",
    "                # 伪质数：\r\n",
    "                for i in range(t*2, t*threshold+1,t):\r\n",
    "                    # 和小于threshold的数相乘，构造低倍合数；\r\n",
    "                    if i>n:break\r\n",
    "                    unions[find(i)] = t \r\n",
    "                else:\r\n",
    "                    for p in primes:\r\n",
    "                        # 和小于自身的伪质数相乘，构造高倍合数\r\n",
    "                        i = t*p\r\n",
    "                        if i>n:break\r\n",
    "                        unions[i] = unions[p] = t\r\n",
    "                    else:\r\n",
    "                        if t*t<=n:\r\n",
    "                            primes.append(t)\r\n",
    "                            unions[t*t] = find(t)\r\n",
    "            else:\r\n",
    "                # 非伪质数：\r\n",
    "                for p in primes:\r\n",
    "                    # 和小于自己伪质因数的伪质数相乘，构造高倍合数；\r\n",
    "                    if t*p>n:break\r\n",
    "                    unions[t*p] = unions[find(t)] = find(p)\r\n",
    "                    if not t%p:break\r\n",
    "        return [find(L)==find(R) for L,R in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "class UF:\n",
    "    def __init__(self,n):\n",
    "        self.comp_cnt = n\n",
    "        self.fa = [i for i in range(n)]\n",
    "        self.sz = [1 for _ in range(n)]\n",
    "    def find(self,x):\n",
    "        return x if self.fa[x]==x else self.find(self.fa[x])\n",
    "    def union(self,x,y)->bool:\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:\n",
    "            return False\n",
    "        if self.sz[x]<self.sz[y]:\n",
    "            x,y = y,x\n",
    "        self.fa[y] = x\n",
    "        self.sz[x]+=self.sz[y]\n",
    "        self.comp_cnt-=1\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        uf = UF(n+1)\n",
    "        for i in range(threshold+1,n+1):\n",
    "            for j in range(2*i,n+1,i):\n",
    "                uf.union(i,j)\n",
    "\n",
    "\n",
    "        ans = []\n",
    "        \n",
    "        for a,b in queries:\n",
    "            ans.append(uf.find(a) == uf.find(b))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.n = n\n",
    "        self.fa = list(range(n))\n",
    "        self.size = [1] * n\n",
    "        self.count = n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.fa[x] != x:\n",
    "            self.fa[x] = self.find(self.fa[x])\n",
    "        return self.fa[x]\n",
    "\n",
    "    def union(self, x, y):\n",
    "        fx, fy = self.find(x), self.find(y)\n",
    "        if fx == fy:\n",
    "            return False\n",
    "        if self.size[fx] < self.size[fy]:\n",
    "            fx, fy = fy, fx\n",
    "        self.size[fx] += self.size[fy]\n",
    "        self.fa[fy] = fx\n",
    "        self.count -= 1\n",
    "        return True\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        uf = UnionFind(n + 1)\n",
    "        for i in range(threshold + 1, int(n+1/2)):\n",
    "            for j in range(i * 2, n + 1, i):\n",
    "                uf.union(i, j)\n",
    "        ans = []\n",
    "        for u, v in queries:\n",
    "            if uf.find(u) == uf.find(v):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans\n",
    "        ans = []\n",
    "        for u, v in queries:\n",
    "            if uf.find(u) == uf.find(v):\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        fa=[0]*(n+1)\n",
    "        def find(x):\n",
    "            nonlocal fa\n",
    "            if x==fa[x]:\n",
    "                return x\n",
    "            fa[x]=find(fa[x])\n",
    "            return fa[x]\n",
    "        def unionf(x,y):\n",
    "            nonlocal fa\n",
    "            fa[fa[y]]=fa[x]\n",
    "            fa[y]=fa[x]\n",
    "        for i in range(1,n+1):\n",
    "            fa[i]=i\n",
    "        for i in range(1,n+1):\n",
    "            k=1\n",
    "            while k*k<=i:\n",
    "                if i%k==0 and k>threshold:\n",
    "                    find(k)\n",
    "                    find(i)\n",
    "                    unionf(k,i)\n",
    "                if i%k==0 and i//k>threshold:\n",
    "                    find(i//k)\n",
    "                    find(i)\n",
    "                    unionf(i,i//k)\n",
    "                k+=1\n",
    "        return [find(a)==find(b)for a,b in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        if threshold==0:\n",
    "            return [True]*len(queries)\n",
    "        fa=[ i for i in range(n+2)]\n",
    "        def find(x:int)->int:\n",
    "            while x!=fa[x]:\n",
    "                fa[x]=fa[fa[x]]\n",
    "                x=fa[x]\n",
    "            return x\n",
    "        for i in range(threshold+1,n+1):\n",
    "            j=2\n",
    "            while i*j<=n:\n",
    "                fai=find(i)\n",
    "                faj=find(i*j)\n",
    "                fa[fai]=faj\n",
    "                j+=1\n",
    "        ans=[]\n",
    "        for x,y in queries:\n",
    "            fax=find(x)\n",
    "            fay=find(y)\n",
    "            if fax==fay:\n",
    "                ans.append(True)\n",
    "            else:\n",
    "                ans.append(False)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self,n):\n",
    "        self.parent=list(range(n))\n",
    "        self.size=[1]*n\n",
    "\n",
    "    def find(self,x):\n",
    "        if x==self.parent[x]:\n",
    "            return x\n",
    "        self.parent[x]=self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self,x,y):\n",
    "        x = self.find(x)\n",
    "        y = self.find(y)\n",
    "        if x==y:return\n",
    "        if self.size[x]<self.size[y]:\n",
    "            x,y=y,x\n",
    "        self.parent[y]=x\n",
    "        self.size[x]+=self.size[y]\n",
    "\n",
    "    def connected(self,x,y):\n",
    "        return self.find(x)==self.find(y)\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        uf = UnionFind(n+1)\n",
    "        for i in range(threshold+1,n+1):\n",
    "            for j in range(1,n//i):\n",
    "                uf.union(i*j,i*(j+1))\n",
    "        ans=[]\n",
    "        for x,y in queries:\n",
    "            ans.append(uf.connected(x,y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        parent, rank = list(range(n + 1)), [1] * (n + 1)\n",
    "        def myfind(i):\n",
    "            if parent[i] != i:\n",
    "                parent[i] = myfind(parent[i])\n",
    "            return parent[i]\n",
    "        def myunion(i, j):\n",
    "            pi, pj = myfind(i), myfind(j)\n",
    "            if pi == pj:\n",
    "                return\n",
    "            if rank[pi] < rank[pj]:\n",
    "                pi, pj = pj, pi\n",
    "            parent[pj] = pi\n",
    "            if rank[pi] == rank[pj]:\n",
    "                rank[pi] += 1\n",
    "            return\n",
    "        for i in range(threshold + 1, n + 1):\n",
    "            for j in range(2, n + 1):\n",
    "                if i * j > n:\n",
    "                    break\n",
    "                myunion(i, i * j)\n",
    "        ans = []\n",
    "        for i, j in queries:\n",
    "            ans.append(myfind(i) == myfind(j))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\r\n",
    "        # 并查集\r\n",
    "        unions = list(range(n+1))\r\n",
    "        def find(i):\r\n",
    "            if (i!=unions[i]):\r\n",
    "                unions[i] = find(unions[i])\r\n",
    "            return unions[i]\r\n",
    "                \r\n",
    "        for t in range(threshold+1,n//2+1):\r\n",
    "            if unions[t]!=t:continue\r\n",
    "            for i in range(t*2,n+1,t):\r\n",
    "                unions[find(i)] = t\r\n",
    "        return [find(L)==find(R) for L,R in queries]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.p = list(range(n))\n",
    "        self.size = [1] * n\n",
    "\n",
    "    def find(self, x):\n",
    "        if self.p[x] != x:\n",
    "            self.p[x] = self.find(self.p[x])\n",
    "        return self.p[x]\n",
    "\n",
    "    def union(self, a, b):\n",
    "        pa, pb = self.find(a), self.find(b)\n",
    "        if pa == pb:\n",
    "            return False\n",
    "        if self.size[pa] > self.size[pb]:\n",
    "            self.p[pb] = pa\n",
    "            self.size[pa] += self.size[pb]\n",
    "        else:\n",
    "            self.p[pa] = pb\n",
    "            self.size[pb] += self.size[pa]\n",
    "        return True\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        uf = UnionFind(n + 1)\n",
    "        for a in range(threshold + 1, n + 1):\n",
    "            for b in range(a + a, n + 1, a):\n",
    "                uf.union(a, b)\n",
    "        return [uf.find(a) == uf.find(b) for a, b in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "\n",
    "        if not threshold: #任意两个自然数都有公约数1，这种情况一定都是True\n",
    "            return [True]*len(queries)\n",
    "\n",
    "        def find(index: int) -> int: #并查集模板\n",
    "            if parent[index] != index:\n",
    "                parent[index] = find(parent[index])\n",
    "            return parent[index]\n",
    "        \n",
    "        def union(index1: int, index2: int):\n",
    "            parent[find(index1)] = find(index2)\n",
    "\n",
    "        parent = list(range(n+1))\n",
    "        out = set() #out表示已出局，out里的数的倍数是已经遍历合并过的\n",
    "\n",
    "        for p in range(threshold+1,n+1):\n",
    "            if p not in out:\n",
    "                num = 2*p #一定要从2*p开始！不要因为担心TLE而从p*p开始，从p*p开始只要p不是素数就会漏合并！\n",
    "                while num<=n: #注意超过n的数于本题没有意义，及时退出循环\n",
    "                    union(num,p)\n",
    "                    out.add(num)  # num不是素数，也有超过threshold的因子，以后遇到num就跳过\n",
    "                    num+=p\n",
    "        \n",
    "        return [find(x)==find(y) for x,y in queries] #预处理结束，依次查询就得到答案"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        if threshold == 0:\n",
    "            return [True] * len(queries)\n",
    "        con = defaultdict(list)\n",
    "        for i in range(threshold + 1, n + 1):\n",
    "            for j in range(i * 2, n + 1, i):\n",
    "                con[i].append(j)\n",
    "                con[j].append(i)\n",
    "        ref = [i for i in range(n + 1)]\n",
    "        def dfs(i, x):\n",
    "            if ref[i] == i:\n",
    "                ref[i] = x\n",
    "                for j in con[i]:\n",
    "                    dfs(j, x)\n",
    "        for i in range(threshold + 1, n + 1):\n",
    "            dfs(i, i)\n",
    "        return [ref[i] == ref[j] for i, j in queries]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class PrimeTable:\n",
    "    def __init__(self, n=int((10**9)**0.5)+3) -> None:\n",
    "        #值域1e9的话考虑质因子，只需小于等于(10**9)**0.5的质数即可\n",
    "        #任意一个正整数n最多只有一个质因子大于根号n\n",
    "        self.n = n\n",
    "        self.primes = [] #小于等于n的所有质数\n",
    "        self.min_div = [0] * (n+1)\n",
    "        self.min_div[1] = 1\n",
    " \n",
    "        mu = [0] * (n+1)\n",
    "        phi = [0] * (n+1)\n",
    "        mu[1] = 1\n",
    "        phi[1] = 1\n",
    " \n",
    "        for i in range(2, n+1):\n",
    "            if not self.min_div[i]:\n",
    "                self.primes.append(i)\n",
    "                self.min_div[i] = i\n",
    "                mu[i] = -1\n",
    "                phi[i] = i-1\n",
    "            for p in self.primes:\n",
    "                if i * p > n: break\n",
    "                self.min_div[i*p] = p\n",
    "                if i % p == 0:\n",
    "                    phi[i*p] = phi[i] * p\n",
    "                    break\n",
    "                else:\n",
    "                    mu[i*p] = -mu[i]\n",
    "                    phi[i*p] = phi[i] * (p - 1)\n",
    "    # x是否质数\n",
    "    def is_prime(self, x:int):\n",
    "        if x < 2: return False\n",
    "        if x <= self.n: return self.min_div[x] == x\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x % i == 0: return False\n",
    "        return True\n",
    "\n",
    "    # x分解质因数:[p, cnt] 质因子p，个数cnt\n",
    "    # 用的yield，当作一个可遍历的数据对象\n",
    "    #一个数一定可以分解为多个质数的连乘积\n",
    "    #n = x^a * y^b * z^c ...  （x,y,z为质因数） n的约数个数=(a+1)(b+1)...(y+1)\n",
    "\n",
    "    def prime_factorization(self, x:int):\n",
    "        for p in self.primes:\n",
    "            if p * p > x: break\n",
    "            if x <= self.n: break\n",
    "            if x % p == 0:\n",
    "                cnt = 0\n",
    "                while x % p == 0: cnt += 1; x //= p\n",
    "                yield p, cnt\n",
    "        while (1 < x and x <= self.n):\n",
    "            p, cnt = self.min_div[x], 0\n",
    "            while x % p == 0: cnt += 1; x //= p\n",
    "            yield p, cnt\n",
    "        if x >= self.n and x > 1:\n",
    "            #小于等于(10**9)**0.5的质数除干净了，如果还大于1\n",
    "            # 那么余下的数一定是一个大于等于n的质数\n",
    "            yield x, 1\n",
    "            \n",
    "    # x的所有因数\n",
    "    def get_factors(self, x:int):\n",
    "        factors = [1]\n",
    "        for p, b in self.prime_factorization(x):\n",
    "            n = len(factors)\n",
    "            for j in range(1, b+1):\n",
    "                for d in factors[:n]:\n",
    "                    factors.append(d * (p ** j))\n",
    "        return factors\n",
    "pt=PrimeTable(10**5+5)\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        fa=list(range(n+5))\n",
    "        def find(a):\n",
    "            if fa[a]!=a:\n",
    "                fa[a]=find(fa[a])\n",
    "            return fa[a]\n",
    "        for x in range(threshold,n+1):\n",
    "            for i in pt.get_factors(x):\n",
    "                if i>threshold:\n",
    "                    fa[find(x)]=find(i)\n",
    "        return [find(x)==find(y) for x,y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import math\n",
    "def f(n ):\n",
    "    ans = {n}\n",
    "    for j in range(1, n+1):\n",
    "        if j*j>n:\n",
    "            break \n",
    "        if n%j==0:\n",
    "            ans.add(j)\n",
    "            ans.add(n//j)\n",
    "        # ans.append(j)\n",
    "    return ans\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, t: int, q: List[List[int]]) -> List[bool]:\n",
    "        s = set()\n",
    "        for j in range(1, n+1):\n",
    "            tmp = f(j)\n",
    "            s|=tmp \n",
    "        # print(s)\n",
    "        s = [j for j in s if j>t]\n",
    "        g = defaultdict(list)\n",
    "        for j in s:\n",
    "            for k in range(1, n+1):\n",
    "                if k%j==0:\n",
    "                    g[k].append(str(j))\n",
    "                    g[str(j)].append(k)\n",
    "     \n",
    "        v = {}\n",
    "        def bfs(x):\n",
    "            s = [x]\n",
    "            v[x] = x\n",
    "            while s:\n",
    "                tmp = []\n",
    "                for j in s:\n",
    "                    for k in g[j]:\n",
    "                        if k not in v:\n",
    "                            v[k] = x \n",
    "                            tmp.append(k) \n",
    "                s = tmp \n",
    "        for j in range(1, n+1):\n",
    "            if j not in v:\n",
    "                bfs(j) \n",
    "        \n",
    "        return [v[x]==v[y] for x, y in q]\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "hashmap = defaultdict(list)\n",
    "N = 10 ** 4 + 1\n",
    "for i in range(1,N):\n",
    "    for j in range(i,N,i):\n",
    "        hashmap[j].append(i)\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        parents = list(range(n+1))\n",
    "        \n",
    "        def find(x):\n",
    "            if x != parents[x]:\n",
    "                parents[x] = find(parents[x])\n",
    "            return parents[x]\n",
    "        \n",
    "        def union(u,v):\n",
    "            x , y = find(u) , find(v)\n",
    "            if x != y:\n",
    "                parents[x] = y\n",
    "        \n",
    "        for u in range(threshold+1,n+1):\n",
    "            for v in hashmap[u]:\n",
    "                if v > threshold:\n",
    "                    union(u,v)\n",
    "\n",
    "        ans = []\n",
    "        for u , v in queries:\n",
    "            ans.append(find(u) == find(v))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        p = [i for i in range(n + 1)]\n",
    "        def find(i):\n",
    "            if p[i] != i:\n",
    "                p[i] = find(p[i])\n",
    "            return p[i]\n",
    "        def merge(i, j):\n",
    "            pi, pj = find(i), find(j)\n",
    "            p[pi] = pj\n",
    "        \n",
    "        for base in range(threshold + 1, n // 2 + 1):\n",
    "            cur = base * 2\n",
    "            while cur <= n:\n",
    "                merge(base, cur)\n",
    "                cur += base\n",
    "\n",
    "        ans = [False] * len(queries)\n",
    "        for i, (x, y) in enumerate(queries):\n",
    "            ans[i] = (find(x) == find(y))\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self, n):\n",
    "        self.parent = [i for i in range(n + 1)]\n",
    "        \n",
    "    def find(self, x):\n",
    "        if self.parent[x] != x:\n",
    "            self.parent[x] = self.find(self.parent[x])\n",
    "        return self.parent[x]\n",
    "    \n",
    "    def union(self, x, y):\n",
    "        rootX = self.find(x)\n",
    "        rootY = self.find(y)\n",
    "        if rootX != rootY:\n",
    "            self.parent[rootX] = rootY\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        uf = UnionFind(n)\n",
    "        \n",
    "        for z in range(threshold + 1, n + 1):\n",
    "            multiple = 2\n",
    "            while z * multiple <= n:\n",
    "                uf.union(z, z * multiple)\n",
    "                multiple += 1\n",
    "                \n",
    "        return [uf.find(x) == uf.find(y) for x, y in queries]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def areConnected(self, n: int, threshold: int, queries: List[List[int]]) -> List[bool]:\n",
    "        parent = list(range(n + 1))\n",
    "\n",
    "        def find(x):\n",
    "            if parent[x] != x:\n",
    "                parent[x] = find(parent[x])\n",
    "            return parent[x]\n",
    "\n",
    "        def union(x, y):\n",
    "            root_x, root_y = find(x), find(y)\n",
    "            if root_x != root_y:\n",
    "                parent[root_x] = root_y\n",
    "\n",
    "        def isConnected(x, y):\n",
    "            return find(x) == find(y)\n",
    "\n",
    "        is_prime = [1] * (n + 1)\n",
    "        for i in range(threshold + 1, n + 1):\n",
    "            if is_prime[i]:\n",
    "                for j in range(i * 2, n + 1, i):\n",
    "                    union(i, j)\n",
    "                    is_prime[j] = 0\n",
    "\n",
    "        res = []\n",
    "        for a, b in queries:\n",
    "            res.append(isConnected(a, b))\n",
    "\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
